// 46. 全排列
class Solution {
public:
    vector<vector<int>> ret;
    void dfs(vector<int>& nums, int x)
    {
        if(x == nums.size() - 1)
        {
            ret.push_back(nums);
            return;
        }
        for(int i = x; i < nums.size(); ++i)
        {
            swap(nums[i], nums[x]);
            dfs(nums, x+1);
            swap(nums[i], nums[x]);
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums, 0);
        return ret;
    }
};

// 47. 全排列 II
class Solution {
public:
    vector<vector<int>> ret;
    void dfs(vector<int>& nums, int x)
    {
        if(x == nums.size()-1)
        {
            ret.push_back(nums);
            return;
        }
        set<int> st; // 检查重复
        for(int i = x; i < nums.size(); ++i)
        {
            if(st.find(nums[i]) != st.end()) continue;
            st.insert(nums[i]);
            swap(nums[i], nums[x]);
            dfs(nums, x+1);
            swap(nums[i], nums[x]);
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        dfs(nums, 0);
        return ret;
    }
};

// 11. 盛最多水的容器
class Solution {
public:
    int min(int x, int y)
    {
        return x < y ? x : y;
    }
    int maxArea(vector<int>& height) {
        int max = 0, left = 0, right = height.size() - 1;
        while(left < right)
        {
            int area = min(height[left], height[right])*(right-left);
            if(area > max) max = area;
            if(height[left] < height[right])
                left++;
            else
                right--;
        }
        return max;
    }
};